package com.maltys.greedy;

/**
 * @author malty
 * @link <a href="https://leetcode.cn/problems/gas-station/">加油站</a>
 */
public class GasStation {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalSum = 0;
        int sum = 0;
        int startIdx = 0;
        for (int i = 0; i < cost.length; i++) {
            sum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if (sum < 0) {
                sum = 0;
                startIdx = (i + 1) % cost.length;
            }
        }
        return totalSum >= 0 ? startIdx : -1;
    }
}
